The invention relates generally to reduced keyboard systems, and more specifically to reduced keyboard systems generating text composed of the hiragana, katakana and kanji characters of the Japanese language.
For many years, portable computers have been getting smaller and smaller. The principal size-limiting component in the effort to produce a smaller portable computer has been the keyboard. If standard typewriter-size keys are used, the portable computer must be at least as large as the keyboard. Miniature keyboards have been used on portable computers, but the miniature keyboard keys have been found to be too small to be easily or quickly manipulated by a user.
Incorporating a full-size keyboard in a portable computer also hinders true portable use of the computer. Most portable computers cannot be operated without placing the computer on a flat work surface to allow the user to type with both hands. A user cannot easily use a portable computer while standing or moving. In the latest generation of small portable computers, called Personal Digital Assistants (PDAs) or palm-sized computers, companies have attempted to address this problem by incorporating handwriting recognition software in the device. A user may directly enter text by writing on a touch-sensitive panel or screen. This handwritten text is then converted by the recognition software into digital data. Unfortunately, in addition to the fact that printing or writing with a pen is in general slower than typing, the accuracy and speed of the handwriting recognition software has to date been less than satisfactory. In the case of the Japanese language, with its large number of complex characters, the problem becomes especially difficult. To make matters worse, today""s handheld computing devices which require text input are becoming smaller still. Recent advances in two-way paging, cellular telephones, and other portable wireless technologies has led to a demand for small and portable two-way messaging systems, and especially for systems which can both send and receive electronic mail (xe2x80x9ce-mailxe2x80x9d).
It would therefore be advantageous to develop a keyboard for entry of text into a computer device that is both small and operable with one hand while the user is holding the device with the other hand. Prior development work has considered use of a keyboard that has a reduced number of keys. As suggested by the keypad layout of a touch-tone telephone, many of the reduced keyboards have used a 3-by-4 array of keys. A number of the keys in the array are associated with multiple characters. There is therefore a need for a method for the user to indicate which of the characters associated with a given key is the desired character.
One suggested approach for unambiguously specifying hiragana characters entered on a reduced keyboard requires the user to enter two or more keystrokes to specify each kana. The keystrokes may be entered either simultaneously (chording) or in sequence (multiple-stroke specification). Neither chording nor multiple-stroke specification has produced a keyboard having adequate simplicity and efficiency of use. Multiple-stroke specification is inefficient, and chording is often complicated to learn and use.
Each syllable in the Japanese syllabary consists of either a single vowel, or a consonant followed by a vowel. There are two exceptions: the syllable  which has no vowel, and the xe2x80x9csmallxe2x80x9d  which is used to indicate the xe2x80x9cdoublingxe2x80x9d or xe2x80x9chardeningxe2x80x9d of the pronunciation of the following consonant. These syllables can be written as hiragana (commonly used when writing native Japanese words) or katakana (commonly used when writing words of foreign origin). The term kana is used to refer to either hiragana or katakana. The syllabary is commonly represented as a table of rows and columns (shown in FIG. 20), wherein each row may have up to five entries in columns corresponding to the five Japanese vowels  and . Each row corresponds to an initial consonant, although a given consonant may undergo sound changes for certain entries in a row (e.g. s(a) = greater than sh(i) ; t(a) = greater than ts(u) ; etc.). The first row consists of five syllables corresponding to each of the five vowels with no initial consonant. The 8th row consists of the palatalized vowels  and  (YI and YE are not used in modern Japanese). The diacritic marks xe2x80x3 and o are used to indicate changes in the pronunciation of the consonant, generally indicating a change from an unvoiced to a voiced consonant. FIG. 21 shows the basic syllables formed by adding the diacritic marks xe2x80x3 and o to syllables in FIG. 20. Smaller versions of the syllablesr  and  are also used in combination with syllables in the second, or  columns of FIGS. 20 and 21 to represent syllables consisting of the corresponding consonant and the palatalized vowel (e.g.  followed by xe2x80x9csmallxe2x80x9d  to represent  ). These syllables with palatalized vowels are thus written as a pair of kana, as shown in FIG. 22, which includes formns written with diacritic marks.
Lexicographic order in Japanese is generally represented by the sequence of syllables in the first column (corresponding to the vowel A) of FIG. 20:   and , where each of these syllables (except ) represents a sub-class of up to five syllables composed from the vowels  and , in that order. Currently, products such as cellular telephones that require Japanese text input generally use a multiple-stroke specification method wherein each of nine keys is associated with each of the first nine rows ( through ). Multiple strokes on a key are used to indicate which of the syllables of the corresponding row is intended, wherein each additional stroke on a key sequentially changes the character to be output to the character appearing in the next column of FIG. 20 or 21. A separating key or a timeout method is used to allow entry of consecutive characters associated with the same key. A tenth key is used for the syllables  , and the katakana xe2x80x9cboxe2x80x9d symbol, which indicates a vowel-only syllable that repeats the vowel of the preceding syllable. The xe2x80x9csmallxe2x80x9d  and  are also associated with the  key, requiring additional keystrokes to be selected. An additional key is commonly used to add the diacritic marks following a syllable.
Entering Japanese hiragana (or katakana) using a reduced keyboard continues to be a challenging problem. With the current multi-stroking approach as described above, generating a single kana syllable requires an average of at least three keystrokes. Syllables with palatalized vowels which are represented by two characters (i.e. those in FIG. 22 consisting of a syllable from the second, , column of FIG. 20 or 24 followed by a xe2x80x9csmallxe2x80x9d  or ) can require up to eight keystrokes to generate. It would therefore be desirable to develop a reduced keyboard system that tends to minimize the number of keystrokes required to enter hiragana, and is also simple and intuitive to use.
Typing standard Japanese text, which includes Chinese characters (kanji) in addition to kana, on a reduced keyboard is an even more challenging problem. Entering text on a standard computer with a full keyboard and a large display is generally achieved by first typing the pronunciation of the desired text using the letters of the Latin alphabet (called xe2x80x9cromajixe2x80x9d in Japanese) corresponding to each hiragana syllable as shown in FIGS. 20-22. As the letters are typed, the input is automatically converted to the corresponding hiragana syllables and displayed on the screen. In many cases, the user then needs to convert the text which is initially displayed as hiragana into the specific textual interpretation desired. The hiragana that are displayed represent the phonetic reading of the combination of kanji and hiragana that the user actually wants to enter, and which conveys the user""s intended meaning. Due to the large number of homophones in the Japanese language, there can be a number of possible meaningful combinations of kanji and hiragana that correspond to the hiragana input by the user. On a standard computer, a number of these alternative conversions can be displayed where, for example, each alternative is associated with a numeric key so that pressing the key converts the input hiragana to the displayed kanji interpretation. Additional complications arise when trying to implement this process on a small hand-held device due to the limited display size and the small number of keys available.
An alternative approach for specifying hiragana entered on a reduced keyboard allows the user to enter each hiragana with a single keystroke. Each key of the reduced keyboard is associated with multiple hiragana characters. As a user enters a sequence of keys, there is therefore ambiguity in the resulting output since each keystroke may indicate one of several hiragana. The system must therefore provide a means by which the user can efficiently indicate which of the possible interpretations of each keystroke was intended. Several approaches have been suggested for resolving the ambiguity of the keystroke sequence.
A number of suggested approaches for determining the correct character sequence that corresponds to an ambiguous keystroke sequence are summarized in the article xe2x80x9cProbabilistic Character Disambiguation for Reduced Keyboards Using Small Text Samples,xe2x80x9d published in the Journal of the International Society for Augmentative and Alternative Communication by John L. Arnott and Muhammad Y. Javad (hereinafter the xe2x80x9cAmott articlexe2x80x9d). The Arnott article notes that the majority of disambiguation approaches employ known statistics of character sequences in the relevant language to resolve character ambiguity in a given context. That is, existing disambiguating systems statistically analyze ambiguous keystroke groupings as they are being entered by a user to determine the appropriate interpretation of the keystrokes. The Arnott article also notes that several disambiguating systems have attempted to use word level disambiguation to decode text from a reduced keyboard. Word level disambiguation processes complete words by comparing the entire sequence of received keystrokes with possible matches in a dictionary after the receipt of an unambiguous character signifying the end of the word. The Arnott article discusses many of the disadvantages of word-level disambiguation. For example, word level disambiguation oftentimes fails to decode a word correctly, because of the limitations in identifying unusual words and the inability to decode words that are not contained in the dictionary. Because of the decoding limitations, word level disambiguation does not give error-free decoding of unconstrained English text with an efficiency of one keystroke per character. The Arnott article therefore concentrates on character level disambiguation rather than word level disambiguation, and indicates that character level disambiguation appears to be the most promising disambiguation technique. However, in contrast to alphabetic languages, each hiragana character in Japanese represents a syllable, rather than a single letter that represents what is essentially a phoneme. For this reason, character level disambiguation is inefficient in the Japanese language because there are almost no constraints on possible sequences of hiragana, and the probability distribution of hiragana sequences is not skewed enough for this approach to be effective.
Still another suggested approach is disclosed in a textbook entitled Principles of Computer Speech, authored by I. H. Witten, and published by Academic Press in 1982 (hereinafter the xe2x80x9cWitten approachxe2x80x9d). Witten discusses a system for reducing ambiguity from text entered using a telephone touch pad. Witten recognizes that for approximately 92% of the words in a 24,500 word English dictionary, no ambiguity will arise when comparing the keystroke sequence with the dictionary. When ambiguities do arise, however, Witten notes that they must be resolved interactively by the system presenting the ambiguity to the user and asking the user to make a selection between the number of ambiguous entries. A user must therefore respond to the system""s prediction at the end of each word. Such a response slows the efficiency of the system and increases the number of keystrokes required to enter a given segment of text.
In the case of the Japanese language, users of word processing software are accustomed to having to select from a number of ambiguous interpretations following the entry of a word due to the large number of homophones in the language. The same sequence of kana can frequently be converted to two or more different kanji interpretations. Thus, after entering a sequence of kana, the user is generally required to select the desired kanji conversion from a set of possible choices, and often is also required to somehow confirm that the correct conversion was selected. When the hiragana are entered using a reduced keyboard, there is also ambiguity as to what the user actually intends as the sequence of hiragana to be converted to kanji. As a result, the number of possible interpretations is greatly increased.
Disambiguating an ambiguous keystroke sequence continues to be a challenging problem. As noted in the publications discussed above, satisfactory solutions that minimize the number of keystrokes required to enter a segment of text have failed to achieve the necessary efficiencies to be acceptable for use in a portable computer. It would therefore be desirable to develop a disambiguating system that resolves the ambiguity of entered keystrokes while minimizing the total number of keystrokes required, within the context of a simple and easy to understand user interface. Such a system would thereby maximize the efficiency of text entry.
An effective reduced keyboard input system for the Japanese language must satisfy all of the following criteria. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, must be easy for a native speaker to understand and learn to use. Second, the system must tend to minimize the number of keystrokes required to enter text in order to enhance the efficiency of the reduced keyboard system. Third, the system must reduce the cognitive load on the user by reducing the amount of attention and decision-making required during the input process. Fourth, the approach should minimize the amount of memory and processing resources needed to implement a practical system.
Kisaichi et al. [JP 8-314920; U.S. Pat. No. 5,786,776; EP 0 732 646 A2] disclose an approach wherein the keys 1-0 of a telephone keypad are labeled with the hiragana syllables {}, {}, {}, {}, {}, {}, {}, {}, {}, and {}, respectively. This corresponds to what is the de facto standard for Japanese telephone keypads wherein the keys 1-9 of the telephone keypad are labeled with the hiragana syllables   and  respectively. The single hiragana appearing on each key represents the complete set of hiragana assigned to that key, corresponding to the entire row of hiragana appearing in FIG. 20 in which the single hiragana appears in the first column. The 0 key is often labeled explicitly with {}.
Kisaichi et al. disclose a word-level disambiguation approach, wherein the user ambiguously inputs a sequence of characters (hiragana) by pressing the key with which each character is associated a single time. At the end of each input sequence, the user presses a xe2x80x9cConversion/Next Candidatexe2x80x9d key to display the first textual interpretation of one of the possible sequences of hiragana associated with the input key sequence. Kisaichi et al. disclose a dictionary structure wherein all textual interpretations of a given input key sequence are stored consecutively in a contiguous block of memory. Each additional press of the xe2x80x9cConversion/Next Candidatexe2x80x9d key displays the next textual interpretation stored in the dictionary, if one exists. If no more textual interpretations exist, an error message is displayed and optional anomaly processing may be performed. When the desired textual interpretation is displayed, a special xe2x80x9cConfirmationxe2x80x9d key must be pressed to confirm that the desired text has been displayed before the user can go on to enter the next text object.
There are a number of difficulties with the approach disclosed by Kisaichi et al. One is that, due to the fact that there is ambiguity both in specification of the hiragana string and in the conversion of each possible hiragana candidate string, there tend to be a very large number of possible textual interpretations of a given key sequence. This can require the user to step through a large number of interpretations using the xe2x80x9cConversion/Next Candidatexe2x80x9d key in order to find the desired interpretation. Further, in stepping through the possible interpretations, the user sees various kanji and/or hiragana strings that correspond to a variety of hiragana strings due to the ambiguity in the input. This can be distracting, and require additional attention from the user in trying to find the desired interpretation. In addition, the database of textual interpretations is arranged such that all data consists only of complete words, and all data for all key sequences of a given length is also stored consecutively in a contiguous block of memory. Kisaichi et al. do not disclose any approach to enable the display of an appropriate stem corresponding to a longer, yet uncompleted word at those points in an input sequence that do not correspond to any completed word. At such points in the input, the system of Kisaichi et al. can only display a default indication of each key entered, such as a numeral or a default letter or character. This is confusing to the user, and fails to provide feedback which is effective in helping the user to confirm that the intended keys have been entered. Finally, the user is required to press the xe2x80x9cConfirmationxe2x80x9d key for each word input, having to enter an additional keystroke for each input. Thus, the system disclosed by Kisaichi et al. fails to satisfy the criteria discussed above.
Another significant challenge facing any application of word-level disambiguation is successfully implementing it on the kinds of hardware platforms on which its use is most advantageous. As mentioned above, such devices include two-way pagers, cellular telephones, and other hand-held wireless communications devices. These systems are battery powered, and consequently are designed to be as frugal as possible in hardware design and resource utilization. Applications designed to run on such systems must minimize both processor bandwidth utilization and memory requirements. These two factors tend in general to be inversely related. Since word-level disambiguation systems require a large database of words to function, and must respond quickly to input keystrokes to provide a satisfactory user interface, it would be a great advantage to be able to compress the required database without significantly impacting the processing time required to utilize it. In the case of the Japanese language, additional information must be included in the database to support the conversion of sequences of kana to the kanji intended by the user.
Another challenge facing any application of word-level disambiguation is providing sufficient feedback to the user about the keystrokes being input. With an ordinary typewriter or word processor, each keystroke represents a unique character which can be displayed to the user as soon as it is entered. But with word-level disambiguation this is often not possible, since each keystroke represents multiple characters, and any sequence of keystrokes may match multiple words or word stems. It would therefore be desirable to develop a disambiguating system that minimizes the ambiguity of entered keystrokes, and also maximizes the efficiency with which the user can resolve any ambiguity which does arise during text entry. One way to increase the user""s efficiency is to provide appropriate feedback following each keystroke, which includes displaying the most likely word following each keystroke, and in cases where the current keystroke sequence does not correspond to a completed word, displaying the most likely stem of a yet uncompleted word.
In order to create an effective reduced keyboard input system for the Japanese language, a system has been designed that does meet all of the criteria mentioned above. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, are easy for a native speaker to understand and learn to use. Second, the system tends to minimize the number of keystrokes required to enter text. Third, the system reduces the cognitive load on the user by reducing the amount of attention and decision-making required during the input process, and by the provision of appropriate feedback. Fourth, the approach disclosed herein tends to minimize the amount of memory and processing resources required to implement a practical system.
The present invention provides a reduced keyboard using word level disambiguation to resolve ambiguities in keystrokes to enter text in the Japanese language. The keyboard may be constructed with full-size mechanical keys, preferably twelve keys arrayed in three columns and four rows as on a standard telephone keypad. Alternatively, the keyboard can be implemented on a display panel which is touch sensitive, wherein contact with the surface of the display generates input signals to the system corresponding to the location of contact.
A plurality of kana characters and symbols are assigned to each of at least several of the keys, so that keystrokes by a user are ambiguous. A user enters a keystroke sequence wherein each keystroke is intended to be the entry of one kana. Each keystroke sequence is thus intended to represent the phonetic reading of a word or common phrase (hereinafter referred to by the Japanese term xe2x80x9cYomikataxe2x80x9d). Because individual keystrokes are ambiguous, the keystroke sequence could potentially match more than one Yomikata with the same number of kana.
The keystroke sequence is processed by comparing the keystroke sequence with one or more stored vocabulary modules to match the sequence with corresponding Yomikata. The various Yomikatas associated with a given key sequence are stored in the vocabulary module in the order determined by their expected frequency of occurrence in general usage, where the expected frequency of a Yomikata is calculated as the sum of the frequencies of occurrence of all possible textual interpretations of that Yomikata (including words composed of kanji, hiragana, katakana, or any combination thereof) in general usage (hereinafter referred to by the Japanese term xe2x80x9cMidashigoxe2x80x9d). In another preferred embodiment, the Yomikata and Midashigo are initially stored in the order determined by their expected frequency of occurrence in general usage, and this order is modified to reflect the frequency of actual usage by the system user. The most frequent Yomikata that matches the sequence of keystrokes and corresponds to at least one completed word or phrase is automatically identified and presented to the user on a display as each keystroke is received. If there is no completed word or phrase whose Yomikata matches the sequence of keystrokes, the most commonly occurring stem of a yet uncompleted word or phrase is automatically identified and presented to the user on the display. The term xe2x80x9cselection listxe2x80x9d is used generically to refer to any list of textual interpretations (either Yomikata or Midashigo) generated by the system corresponding to an input keystroke sequence. On devices with sufficient display area available (hereinafter referred to as xe2x80x9clarge-screen devicesxe2x80x9d), the selection list may be shown (in whole or in part) in a xe2x80x9cselection list regionxe2x80x9d of the display. On such devices, as each keystroke is received, the various Yomikata corresponding to the input sequence are simultaneously presented to the user in a list on the display in descending order of expected frequency in the selection list region. On devices with limited display area, the selection list is maintained internally, and text objects in the list are displayed one at a time in response to activations of a Select key as described below. For each Yomikata in the stored vocabulary module that is associated with one or more alternate textual interpretations, or Midashigo, the Midashigo are stored in order of decreasing frequency of expected occurrence in general usage, so that the most commonly used Midashigo is presented first. As briefly noted above, in an alternate embodiment, the system keeps track of which Midashigo are selected for output by the user most frequently, and modifies the order of presentation to first present the Midashigo most frequently selected.
In accordance with one aspect of the invention, the user presses an unambiguous Select key to delimit an entered keystroke sequence. After receiving the Select key, the disambiguating system automatically selects the most frequently occurring Yomikata and adds the kana to the text being constructed when the user continues to enter additional text. By default, the Yomikata is shown on the display in the form of hiragana, unless the kana is one of the few katakana for which there is no corresponding hiragana (e.g. ). In another embodiment, the Yomikata is displayed in the form of katakana, or, in some of the alternate keyboard arrangements described below, in the form of romaji.
In accordance with another aspect of the invention, the Select key that is pressed to delimit the end of a keystroke sequence is also used to select less commonly occurring Yomikata. If the most commonly occurring Yomikata presented on the display is not the desired Yomikata, the user presses the Select key again to advance from the most frequently occurring Yomikata to the second most frequently used Yomikata, which replaces the Yomikata first displayed. If this is not the desired Yomikata, the user presses the Select key again to advance to the third most frequently used Yomikata, and so on. By repetitively pressing the Select key, the user may therefore select the desired Yomikata from the stored vocabulary module. In accordance with another aspect of the invention, upon reaching the end of the Yomikata found in the stored vocabulary, the first and most frequently occurring Yomikata is again displayed, and the cycle repeats.
In accordance with yet another aspect of the invention, each keystroke of the input sequence is also interpreted as a numeral associated with the key, so that the last item displayed following the associated Yomikata is the number corresponding to the input key sequence. This number may be selected for output, thus eliminating the need for a separate numeric mode in the system.
In accordance with another aspect of the invention, once the user has selected the desired Yomikata corresponding to the input key sequence, if the desired Midashigo is identical to the Yornikata which has been selected and is already shown on the display as kana text (i.e. no conversion is required), the user may simply proceed to press the keys corresponding to the next desired text to be input. No additional confirmation or conversion keystroke is requiredxe2x80x94the selected text has already been provisionally sent to the display for output, and unless it is explicitly changed (e.g. by additional presses of the Select key), it will remain as part of the output text. The user can immediately proceed to enter additional following text, move the text cursor location, or select some other system function. If the desired Midashigo is not the selected Yomikata on the display, i.e., the desired Midashigo consists of kanji, kanji plus hiragana, or katakana, the user presses a Convert key until the desired Midashigo is displayed. If the first (default) Yomikata displayed after the entry of a key sequence is the desired Yomikata, a user need not press the Select key, and may immediately press the Convert key to obtain the desired Midashigo.
The present invention also discloses a method for unambiguously generating the syllables of the Japanese language from ordered pairs of keystrokes on a reduced keyboard in such a way as to meet two of the criteria mentioned above. First, the arrangement of the syllables of the Japanese language (kana) on the keyboard, and the method by which they are generated, are easy for a native speaker to understand and learn to use. Second, the arrangement tends to minimize the number of keystrokes required to unambiguously enter the syllables of the Japanese language. In this aspect of the invention, a sequence of two keystrokes is entered to specify each syllable unambiguously, including the syllables with palatalized vowels shown in FIG. 22 that are written with two kana each.
Input sequences of keystrokes are interpreted as ordered pairs of keystrokes which select a character according to its position in a two-dimensional matrix. The first keystroke of each ordered pair specifies the row of the matrix in which the desired character appears, and the second keystroke of each pair specifies the column. The organization of the characters in the first five columns of the matrix conforms to the manner in which the Japanese syllabary is learned and conceptualized by a native Japanese speaker, as they are shown in FIG. 20. An additional three columns may be organized in a manner that corresponds with the natural model of how the syllables with palatalized vowels are formed (each as a combination of two kana), although these are generally regarded as a separate matrix from the basic syllabary (FIG. 22). Two more columns may be added to handle two special cases (small  and ) that do not fit into the simple patterns of the first eight columns. These two characters can also be handled somewhat differently in a variety of alternate embodiments. The simplicity and logical organization of this matrix approach makes it possible to use the matrix even when there is no display available to provide feedback to the user. When a display is available, the matrix can be used to organize how feedback is provided to make the operation of the system transparent to the user.
The Japanese syllabary includes 108 syllables (counting the xe2x80x9csmallxe2x80x9d   and  as separate syllables from the full-sized   and  since they are written and pronounced in a distinct fashion). There are some additional seldom used syllables, such as the xe2x80x9csmallxe2x80x9d versions of the vowel syllablesr  and  that are primarily used in katakana. These seldom used syllables may also be easily generated by using the matrix system as discussed above. Of the 108 syllables, 37 are generated by simply adding one of the diacritic marks, dakuten (xe2x80x3) or handakuten (o), to one of the other 71 syllables. These 71 syllables without diacritic marks can be logically organized into a single matrix of nine or ten rows and eight to ten columns. A plurality of the keys on the reduced keyboard of the present invention may be labeled with two kana, one representing the consonant associated with a given row of the matrix, and second kana representing the vowel associated with a given column of the matrix.
The organization is logical and intuitive for a native speaker of Japanese for 106 of the 108 syllables, and the method for generating the remaining two syllables, i.e., small , and , is simple and easily learned. Every syllable is generated by a single pair of keystrokes, including syllables with palatalized vowels that are represented by two separate kana. This results in significantly fewer keystrokes than is required by the currently used multiple-stroke method for entering kana on a reduced keyboard. Thus, the present invention provides a reduced keyboard that is easily understood and quickly learned by native speakers of Japanese, and that is efficient in terms of reducing the length of input keystroke sequences.
In yet another aspect of the invention, both ambiguous and unambiguous methods of specification of syllables as described above may be combined to achieve greater efficiencies in the input method. In one preferred embodiment, the first syllable of each word or phrase to be generated is specified unambiguously by entering an ordered pair of keystrokes using the matrix approach as discussed above, while the remaining syllables of the word or phrase are specified ambiguously with a single keystroke for each syllable using the word level disambiguation method.
In accordance with yet another aspect of the invention, multiple interpretations of the keystroke sequence are provided to the user in the selection list. The keystroke sequence is interpreted as forming one or more words, where the most frequently occurring corresponding word is displayed, and where other corresponding words may also be displayed in a selection list. Simultaneously, the keystroke sequence is interpreted as a number (as explained above), as a word entered using the two-stroke method of the present system or the well-known multiple-stroke specification method, and as a stem of an uncompleted word. On large-screen devices, the multiple interpretations are simultaneously presented to the user in a selection list region for each keystroke of a keystroke sequence entered by the user. On any device, the user may select from the alternate interpretations by pressing the Select key a number of times.
According to a further aspect of the invention, users explicitly disambiguate an already completed key sequence by entering a respell mode. In respell mode, digit keystrokes are taken to be the second keystroke of a two-stroke explicit entry (the first keystroke being the keystroke in the existing key sequence). A menu giving the keystrokes which are available for the current character position and the character they will generate is automatically presented. The cursor automatically advances to the next character with every keystroke. The selection list, pruned to show only the objects compatible with the new explicit characters, is continually updated and presented. The mode is exited when the last character is disambiguated or when the user presses Select or Convert, those keys having their normal function in this mode, also.
In accordance with still another aspect of the invention, the principle database of words and phrases that is used to disambiguate input key sequences is preferably stored in a vocabulary module using tree data structures. Words corresponding to a particular keystroke sequence are constructed from data stored in the tree structure in the form of instructions. The instructions modify the set of words and word stems associated with the immediately preceding keystroke sequence (i.e., the particular keystroke sequence without the last keystroke) to create a new set of words and word stems associated with the keystroke sequence to which the current keystroke has been appended. Constructing words in this manner reduces the storage space of the vocabulary module, since the instructions to build word stems are stored only once, at the top of the tree structure, and are shared by all words constructed from the word stems. The tree structure also greatly reduces processing requirements, since no searching is required to locate stored objects, i.e., words and word stems, for example. The objects stored in the tree data structure may contain frequency or other ranking information which indicates which object is to be displayed first to the user, thus further reducing processing requirements. Furthermore, this tree data structure may be modified using a special algorithm which further compresses the total size required for the database, without engendering an additional processing burden when the database is utilized to retrieve objects associated with keystroke sequences.
In yet another aspect of the present invention, the tree data structure includes two types of instructions. Primary instructions create the Yomikata of the words and phrases stored in a vocabulary module which consist of sequences of kana corresponding to the pronunciation of the words and phrases. Corresponding to each Yomikata is a list of secondary instructions which create the Midashigo associated with each Yomikata. Each Yomikata is created by a primary instruction which modifies one of the Yomikata associated with the immediately preceding keystroke sequence. Likewise, each Midashigo is created by a secondary instruction which modifies one of the Midashigo associated with the Yomikata which was modified by the primary instruction with which the secondary instruction is associated.
The internal, logical representation of the keys in an embodiment need not mirror the physical arrangement represented by the labels on the actual keys. For example, in a database constructed to represent a Japanese vocabulary module, four additional characters () may also be associated with the key labeled only with the single character . Similarly, characters with special diacritic marks such as the dakuten and handakuten (xe2x80x3 and o) can also be associated with a key. For example, the characters (and ) may also be associated with the key labeled only with the single character . This allows the user to easily recall and type words containing characters with diacritic marks, performing only one key activation per character, simply by activating the logically associated physical key for the associated accented character.
Furthermore, in yet another aspect of the invention, greater efficiencies in database compression are achieved by storing each kanji character only once in the database structure for any particular associated reading. In general, a database may include a number of different instances of the same kanji with the same reading (e.g. the kanji  (read as ) in  () and  ()). In one preferred embodiment, starting immediately from the root of the tree structure, each reading associated with a given kanji is included in the database, together with a full specification of the code for the kanji. Other occurrences of the kanji having the same reading in the database (not starting immediately from the root of the tree structure) are defined though an indirect reference, which specifies the relative position of the fully specified kanji in the list of Midashigo associated with the reading starting immediately from the root of the tree structure.
Though the tree data structure described above is very efficient for encoding and accessing a large word list, it will be evident to one of ordinary skill in the art that vocabulary modules used in this invention can have other structures. In particular, an embodiment includes a mechanism for users to add words to the recognized set. Since the database with the bulk of the language is often stored in read-only memory, it cannot be modified at run time. Instead, new words are stored in a separate user database which, due to the small number of words involved, is most efficiently stored as a simple list of Yomikata and associated Midashigos.
The combined effects of the assignment of multiple characters to keys, the delimiting of words using a Select key, the selection of the desired Yomikata using a Select key optionally followed by the selection of the desired Midashigo using a Convert key, the presentation of the most commonly occurring word or word stem as the first word in the selection list, the inclusion of multiple interpretations in the selection list, the automatic addition of a selected word to a sentence by the first keystroke of the following word, the ability to compress a large database for disambiguation without incurring any significant processing penalties, and the ability to generate words with characters with diacritic marks by typing the key associated with the characters without a diacritic mark produces a surprising result: for the Japanese language, well over 99% of words found in a representative corpus of text material can be typed on the system with extremely high efficiency. On average, in comparison with entering text on a full keyboard containing one key for each possible basic kana (i.e. 50 keys including those shown in FIG. 20 plus the xe2x80x9csmallxe2x80x9d ,  and ), only 0.61 additional keystrokes per word are required using the reduced keyboard of the present invention with only twelve keys. Compared with a conventional keyboard where kana are entered by spelling the desired word using romaji, on average the system actually requires even fewer keystrokes. When words include characters with diacritics, additional keystroke savings can be achieved. When the words are presented in frequency of use order, the desired word is most often the first word presented and in many cases is the only word presented. The user can then proceed to enter the next word with no additional keystrokes required. High speed entry of text is therefore achieved using a keyboard having a small number of keys.
Japanese is a highly agglutinative language. As such morphemes (inflections, articles, prepositions, etc.), which would be represented as separate words in Indo-European languages, are written as suffixes to words in Japanese. Therefore, it is difficult to get satisfactory coverage of all words a user would like to input without dynamically creating words from lists of valid stems and suffixes. To address this, an alternate embodiment of the present invention provides one or more base trees, with information about the roots of words (lexemes), and one or more suffix trees, with information about the suffixes of words (morphemes). In addition to generating the roots and suffixes themselves, these trees also contain information necessary to allow only legal combinations of roots and suffixes and to properly order the generated complete words (roots and/or roots with suffixes). The process of dynamically generating words from roots and suffixes is referred to in this document as xe2x80x9cauto-inflection.xe2x80x9d
In a system with auto-inflection and a user database, another aspect of this invention greatly expands the power of user-defined words by providing a full set of inflections of them. The suffix class of the user-defined word can be assumed to be the most likely class (a general noun) or it can be specified by the user using a simple menu interface or other method known to the art.
The reduced keyboard disambiguation system disclosed herein reduces the size of the computer or other device that incorporates the system. The reduced number of keys allows a device to be constructed to be held by the user in one hand, while being operated with the other hand. The disclosed system is particularly advantageous for use with cellular telephones, PDAs, two-way pagers, or other small electronic devices that benefit from accurate, high-speed text entry. The system efficiently compresses a large database for disambiguating keystroke sequences without requiring additional processing bandwidth when utilizing the compressed database. The system can provide both efficiency and simplicity when implemented on a touchscreen based device or a device with a limited number of mechanical keys that may also have limited display screen area.